1. Field of the Invention
This invention relates to cryptography, and more particularly, to constructing and enhancing cryptographic mechanisms.
2. Description of Related Art
Cryptographic mechanisms are used in many fields to improve the security of stored and transmitted data and signals, to authenticate data and signals and to provide protection and privacy of data and signals. Cryptographic mechanisms are used, for example, in communication systems such as digital telephone systems (for both audio and video communications) and in data processing systems to maintain privacy and secrecy of stored and transmitted data, and to authenticate signals and data.
The transformation of signals or data so that their contents cannot be determined is called encryption. The re-transformation of an encrypted signal or data to get back the original signal or data is called decryption. The combination of encryption and decryption is called cryptography and is carried out by cryptographic mechanisms. For example, FIG. 1 shows a typical cryptographic mechanism 100. Cryptographic mechanism 100 includes an encryption mechanism component 102 and a decryption mechanism component 104. Data encryption operates via the encryption mechanism 102 on an input signal or data (plaintext) P (via a channel 106) to produce an encrypted output signal or data (ciphertext) C (via a channel 108). Similarly, the ciphertext C is decrypted using the decryption mechanism 104 to produce the plaintext P. Most cryptographic mechanisms 100 use cryptographic keys 110, 112 to select the transformation used in encryption and decryption. A cryptographic mechanism 100 can viewed as a filter, taking a first signal and producing another signal corresponding to the encryption or decryption (as appropriate) of the first signal.
Cryptographic mechanisms can be broadly categorized into two classes, namely stream and block devices. In stream cryptographic mechanisms, the input plaintext is encrypted one unit (e.g., one bit or character) at time. Decryption in these stream devices also takes place one unit at a time. In block cryptographic mechanisms, the plaintext is encrypted (and decrypted) in blocks of units, e.g., 64-bit blocks.
Cryptographic mechanism 100 may be implemented entirely in electronic hardware, entirely in software operating on a computer, or in a hybrid combination of both hardware and software. FIG. 2 is a schematic diagram of a hybrid implementation of cryptographic mechanism 100 which employs one or more cipher mechanisms 114, one or more CPUs 116, and memory 118. Each of the encryption mechanism 102 and the decryption mechanism 104 may have its own cipher mechanism 114, CPU 116, and memory 118, or some or all of these components may be shared. Cipher mechanism 114 implements a particular cipher and may be on its own chip and include its own computer. Other aspects of the cryptographic mechanism 100 are implemented using the CPU 116 and the memory 118, in combination with the cipher mechanism 114.
Cryptographic mechanisms are used in many systems to perform a number of functions, including, but not limited to, authenticating and verifying data (transmitted or stored), hashing data, and encrypting and decrypting messages, data and signals. As examples, a communications system and a computer system, both employing cryptographic mechanisms for various purposes, are described herein. These systems are described only as examples of systems which employ cryptographic mechanisms and of the uses of cryptographic mechanisms in those systems. These examples are not intended to be a complete enumeration of all possible systems in which a cryptographic mechanism of the type described herein could be used, nor are they intended to be a complete enumeration of the various uses of cryptographic mechanisms in those systems.
Cryptographic mechanisms are used in a typical communication system 120, such as shown in FIG. 3(a) to ensure, inter alia, the secrecy and privacy of communications within the system. In communication system 120, communication devices 122 communicate messages over channels 124. Communication devices 122 may, for example, be computer systems, telephones, facsimile devices, or the like, alone or in combination. The channels 124 may, for example, be regular telephone wires, fiber optic cables, radio waves, microwaves, or the like, alone or in combination. The messages transmitted over the channels 124 may be voice or data, they may be video signals, pictures, or any other form of transmittable data.
Many data communication systems are open, having some or all of the channels 124 insecure. This is especially the case when one or more of the channels employs radio waves which are detectable and easily monitored without affecting the communication system itself. For example, in the case where the communication system 120 is a telephone network, with some of the devices 122 being cellular telephones, some of the channels 124 being radio channels, and the messages being telephone conversations, i.e., voice messages, between users of telephones, the contents of the messages which are sent over radio channels 124 can be monitored by listening in on the appropriate broadcast frequency.
To overcome problems presented by open, insecure channels in communication systems, it is desirable to make it difficult, if not impossible, for someone to ascertain the content of a monitored message. To this end, it is desirable to transform or encode messages, prior to their transmittal over open channels, into messages whose contents cannot be determined. Clearly it is necessary to be able to transform an encoded, transmitted message back to its original message so that the intended recipient can determine its contents.
Thus, in order to overcome the insecurity of communication messages between communication devices 122 over open channels 124 in communication system 120, it is desirable to encrypt messages prior to their transmittal by a communication device 122 and to decrypt them upon receipt by another communication device 122. In this way, by the time a message can be intercepted, i.e., by the time a message is available on an open channel, its contents cannot be determined without being decrypted. To this end, with reference to FIGS. 3(a) and 3(b), each communication device 122 has a message generator/receiver 126 connected via internal (secure) channel 128 to cryptographic mechanism 100. (Cryptographic mechanism 100 corresponds to the cryptographic mechanism 100 of FIG. 1.) As noted above, a typical cryptographic mechanism 100 is keyed, that is, it uses a cryptographic key 110 or 112 to control its encryption/decryption functions. Communication between communication devices 122 over open channels 124 takes place via cryptographic mechanisms 100. For example, in a transmit mode, the message generator/receiver 126 of one communication device 122 produces a plaintext message which is sent over internal channel 128 to cryptographic mechanism 120 of that communication device 122. Cryptographic mechanism 100 uses a cryptographic key 110 to control the encryption of the plaintext message, producing a ciphertext message which is transmitted over open channel 124. Anyone intercepting the transmitted ciphertext message would be unable to determine its contents (i.e., the plaintext message) without first decrypting the message. The ciphertext message is sent, via channel 124 to another communication device 122. At the other communication device 122, cryptographic mechanism 100 receives the ciphertext message and decrypts it using the same cryptographic key 112, producing the plaintext message. The plaintext message is then sent over the internal channel 128 of communication mechanism 122 to the message generator/receiver 126.
The internal channel 128 may be a real channel in a device or it may be a logical (i.e., virtual channel). In other words, the cryptographic mechanism 100 may be integrated with the message generator/receiver 126 in such a way that the actual channel 128 is not physically discernable or it may be a separate device connected via an internal data bus of some sort.
Cryptographic mechanisms are used in computer systems such as computer system 130 shown in FIG. 3(c), having one or more computers 132 connected to each other and to at least one storage device 134 via a bus 136. Storage device 134 may be fixed, e.g., a hard disk, or it may be portable, e.g., a floppy disk, an optical disk, a tape, or the like. Each computer 132 may also have its own local storage device (not shown). In computer system 130, a cryptographic mechanism 100 (FIG. 1) is used, inter alia, to verify data (stored on a computer 132 or a storage device 134, or transmitted between computers 132), to keep data secret and private, and to prevent unauthorized access to data (stored on a storage device 134 or a computer 132, or transmitted between computers 132).
For example, with reference to FIG. 3(c), a computer 132 in computer system 130 stores (via bus 136) data in a file 138 on a storage device 134. In order to prevent unauthorized access to the data in the file 138, whether by other users of the computer system 130, or by someone gaining access to the file 138 in some other way, it is desirable to store the data in an encrypted form. Note that access to the data can be gained by obtaining the storage device 134 or by gaining access to the bus 136 while the data is being transferred from the computer 132 to the storage device 134. To this end, the computer 132 includes a cryptographic mechanism 100 (FIG. 1) for encrypting and decrypting stored data.
As a further example of the use of a cryptographic mechanism, in the communication system 120 of FIG. 3(a), or computer system 130 of FIG. 3(c), or the like, it is sometimes desirable to use only one aspect of the cryptographic mechanism 100. In particular, it is sometimes desirable to use only the encryption mechanism (reference numeral 102 of FIG. 1) to encrypt data in order to authenticate the data. To this end, the cryptographic mechanism 100 can be used to provide an authentification function. Data or signals to be authenticated are encrypted or hashed (controlled by a cryptographic key) by the cryptographic mechanism 100 to produce a value representative of the data. If the data changes then its corresponding encryption value will change, thereby allowing authentification.
In the cryptographic mechanisms described herein, the manner in which keys are provided to the mechanisms is well known and therefore is not described in detail. For example, each communication device 122 or computer 132 may have some means for creating, storing and inputting keys when need, and for providing these keys to their cryptographic mechanisms in a conventional manner.
The above examples (the communications system and the computer system) are only some examples of fields, mechanisms, devices and systems which employ cryptographic mechanisms, and they are not intended to be a complete enumeration of all possible systems in which a cryptographic mechanism of the type described herein could be used.
Cryptographic mechanisms 100 employed in the same system, whether it be a communication system 120, a computer system 130, or the like, must be of the same type in order to be able to function together. This is not to say that the mechanisms must use the same implementations, only that the mechanisms must perform the same encryption and decryption functions. For example, cryptographic mechanism 100 may be implemented entirely in electronic hardware, entirely in software operating on a computer, or in a hybrid combination of hardware and software (as shown above with respect to FIG. 2). Such differently implemented mechanisms can readily be employed in the same system as long as the mechanisms perform the same or compatible encryption and decryption functions.
Throughout this application, including the claims, the term "mechanism" is intended to include all possible implementations (such as electronic hardware, computer implemented software, hybrids, or the like) or the process performed. Thus a cryptographic or cipher mechanism refers to either a process of enciphering and/or deciphering or any implementation (for example, hardware, computer implemented software, hybrid, or the like) for performing the process. Furthermore, the terms "cipher" and "ciphering" are employed to refer generally to both enciphering and deciphering.
To ensure that various cryptographic mechanisms perform the same encryption and decryption functions, various national and international standards have been set for cryptographic mechanisms and techniques. One example is the Data Encryption Standard (DES). DES is a block cipher that encrypts data in 64-bit blocks. DES takes a 64-bit plaintext and a key, effectively 56 bits long, to produce a 64-bit ciphertext. Decryption in DES takes 64-bit blocks of ciphertext and the same key to reproduce 64-bit blocks of plaintext. The effective DES key length is 56 bits (usually the key is expressed as a 64-bit number, with every eighth bit used for parity checking).
DES has been adopted as an American National Standards Institute (ANSI) standard (ANSI X3.92) and, as part of the standard, the National Institute of Standards and Technology (NIST) validates hardware and firmware implementations of DES. This validation confirms that the implementation follows the standard. The standard does not allow software versions of DES, unless they are unchangeably fixed within a hardware device (for example, by using a read-only memory to hold the hardware control instructions which implement the DES cryptographic mechanism). However, uncertified software versions of DES are common.
The security of DES has been questioned and attempts have been made to increase and improve it. Two aspects of DES relating to its security are the key length and the block size.
Doubling the block size of cipher mechanisms using multiple encryptions has been proposed in order to strengthen them. However, proposed techniques are subject to cryptanalysis.
Attempts have been made to improve DES by using multiple DES operations in sequence (using the same or different keys for each round of DES). Unfortunately, double DES (using DES to again encipher a message already encrypted by DES) has been shown to be barely stronger than DES itself. When a known plaintext-ciphertext pair is available, a search of all possible keys for the input operation, and all keys for the output operation will break the system. It has been shown that if DES has certain mathematical properties (namely if DES is a group) then cryptanalysis of DES (that is, breaking DES) would be easier than if it does not have those properties. Further, if DES has those mathematical properties, then multiple encryption would be useless and would actually weaken DES. To date it has not been shown whether DES has those mathematical properties (i.e., whether DES is a group) but most research points away from it having them. Assuming DES is not a group, the result of triple-DES (passing a message through DES three times, with the same or different keys) may be much harder to break than that of DES or double-DES. However, triple-DES is expensive and complex, and may require three hardware DES implementations and interconnecting hardware, or three software DES executions. In general multiple encryption using the same encryption technique and key does not affect the complexity of a brute-force cryptanalysis. Multiple keys are needed to enhance security.
Many other block ciphers have been developed and some of these may eventually overtake or replace DES in usage. The most likely successor to DES at present is a block cipher called IDEA. IDEA operates on 64-bit plaintext blocks using a 128-bit key (more than twice the effective key length of DES). Current software implementations of IDEA are about as fast as DES. A hardware implementation of IDEA encrypts data at a rate of 177 Mbits/second when clocked at 25 MHz. The security of the IDEA cipher is not yet known, and even if it is adopted in some areas, it will be some time before it overtakes DES in use.
In general, the displacement of a commonly-used cipher by a new cipher will not take place until the community of users is satisfied that the new cipher is more secure than the old one. Since ciphers are often implemented by hardware cipher mechanisms, a change in ciphers can be expensive and may require extensive changes to a system employing them. In a large system, with some cryptographic mechanisms implemented in hardware, some in software, and others in hybrid form, changing or updating a cipher is not only costly, but potentially error prone. For example, in the communication system 120 of FIGS. 3(a)-3(b), each of the cryptographic mechanisms 100 in every communication device 122 would have to be replaced. Or in a computer network employing computers 132 as in the computer system 130 of FIG. 3(c), the cryptographic mechanisms 100 on each computer 132 in the system would have to be replaced. On the other hand, when there are widespread suspicions of weakness of an existing highly used cipher, it would be useful to enhance existing systems which use that cipher.